// 集合中使用字符数字编码作为key存储键值时，会出现冲突，就是有些字符的编码相同，导致后面的值被覆盖
// 1.为了解决这个问题，使用分离链接处理，将字符编码key对应的键值通过链表存储
/* 2.线性探查，通过key转为position值，当想向表中某个位置添加一个新元素的时候，如果索引为 position 的位置已经被占据了，152 第 8 章 字典和散列表
就尝试 position+1 的位置。如果 position+1 的位置也被占据了，就尝试 position+2 的位
置，以此类推 */



function defaultEquals(a, b) {
  return a === b;
}
// 链表类，节点类，分离链接结合
class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined
  }
}

class LinkList {
  constructor(erualIsFn = defaultEquals) {
    this.head = null
    this.count = 0
    this.erualIsFn = erualIsFn
  }
  getHead() {
    return this.head
  }
  push(element) {
    let node = new Node(element)
    let current = this.head
    if (this.head == null) {
      this.head = node
    } else {
      while (current.next != null) {
        current = current.next
      }
      current.next = node
    }
    this.count++
  }
  remove(element) {
    let index = this.indexOf(element);
    return this.removeAt(index)
  }
  indexOf(element) {
    let current = this.head;
    for (let i = 0; i <= this.count && current != null; i++) {

      if (this.erualIsFn(element, current.element)) {
        return i
      } else {
        current = current.next
      }
    }
    return -1
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        this.head = current.next
      } else {
        let previous = this.getElementAt(index - 1)
        let current = previous.next
        previous.next = current.next
        // this.head = 
      }
      this.count--;
      return current
    }
    return undefined
  }
  getElementAt(index) {
    let current = this.head
    if (index >= 0 && index < this.count) {
      if (index === 0) {
        return current
      } else {
        for (let i = 0; i < this.index; i++) {
          current = current.next
        }
        return current
      }

    }
    return undefined
  }
}

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}
function defaultToStrFn(key) {
  if (key === null) {
    return "NULL"
  } else if (key === undefined) {
    return "UNDEFINED"
  } else if (typeof key == 'string' || key instanceof String) {
    return key
  }
  return key.toString()

}
class HashTableSeparateChaining {
  constructor(toStrFn = defaultToStrFn) {
    this.table = {}
    this.toStrFn = toStrFn
  }
  loseloseHashCode(key) {
    if (typeof key === 'number') {
      return key
    }
    let strKey = this.toStrFn(key)
    let hash = 0
    for (let i = 0; i < strKey.length; i++) {
      //charCodeAt() 方法可返回指定位置的字符的 Unicode 编码
      hash += strKey.charCodeAt(i)
    }
    return hash % 37
  }
  hashCode(key) {
    return this.loseloseHashCode(key)
  }
  put(key, value) {
    if (key != null && value != null) {
      let keyStr = this.hashCode(key);
      let valuePairList = this.table[keyStr]
      let valuePair = new ValuePair(key, value)
      if (valuePairList == null) {
        this.table[keyStr] = new LinkList()
      }
      this.table[keyStr].push(valuePair)
      return true
    } else {
      return false
    }
  }
  get(key) {
    let position = this.hashCode(key);
    let valuePairList = this.table[position];
    if (valuePairList != null) {
      let current = valuePairList.head
      for (let i = 0; i < valuePairList.count; i++) {
        if (key === current.element.key) {
          return current.element.value
        }
        current = current.next
      }
    } else {
      return undefined
    }
  }
  remove(key) {
    let position = this.hashCode(key);
    let linkList = this.table[position]
    if (linkList != null) {
      let current = linkList.head

      for (let i = 0; i < linkList.count; i++) {
        if (current.element.key === key) {
          linkList.remove(current.element)
          if (linkList.count === 0) {
            delete this.table[position]
          }
        } else {
          current = current.next
        }
      }
      return true
    } else {
      return false
    }

  }
}

let hashTable = new HashTableSeparateChaining()
hashTable.put('Jonathan', 'a.com')
hashTable.put('Jamie', 'a1.com')
hashTable.put('b', 'b.com')

console.log(hashTable.get('b'))
hashTable.remove('Jamie')
console.log(hashTable, '1')